package algorithm

type BiNode struct {
	data int
	parent *BiNode
	left *BiNode
	right *BiNode
}

type BiTree struct {
	root *BiNode
}

func NewBiNode(data int) *BiNode {
	return &BiNode{
		data:   data,
		parent: nil,
		left:   nil,
		right:  nil,
	}
}

func NewBiTree(v int) *BiTree {
	return &BiTree{root: NewBiNode(v)}
}

func (t *BiTree) Insert(v int)  {
	t.insert(t.root,v)
}

func (t *BiTree) insert(node *BiNode,v int) *BiNode {
	if node == nil{
		return NewBiNode(v)
	}
	if node.data>v{
		node.right=t.insert(node.right,v)
	}else if node.data<v{
		node.left=t.insert(node.left,v)
	}
	return nil
}

func (t *BiTree) Search(v int) *BiNode {
	return t.search(t.root,v)
}

func (t *BiTree) search(node *BiNode,v int) *BiNode {
	if node==nil{
		return nil
	}
	if v<node.data{
		return t.search(node.left,v)
	}else if v>node.data{
		return t.search(node.right,v)
	}else {
		return node
	}
}

func (t *BiTree) Delete(v int) *BiNode {
	s := t.search(t.root,v)
	if s!=nil{
		if s.parent!=nil{
			if s.left==nil&&s.right==nil{//叶子节点直接删除
				if s.parent.data<s.data{
					s.parent.right=nil
				}else {
					s.parent.left=nil
				}
			}else if s.left==nil||s.right==nil{//只有一个节点，则直接赋值子节点为父节点的子树
				if s.parent.data<s.data{
					if s.left!=nil{
						s.parent.right=s.left
						s.left.parent=s.parent
					}else if s.right!=nil{
						s.parent.left=s.right
						s.right.parent=s.parent
					}
				}else if s.parent.data>s.data{
					if s.left!=nil{

					}
				}
			}else if s.left!=nil&&s.right!=nil{//有两个子树，则寻找右子树的最小节点替换到当前节点，并把原来的点删除，右子树的最小节点最多只能有一个子节点
				//rightMin:=t.FindMin(s.right)  //找到右子树的最小节点
				if v<s.parent.data{//删除的是左子树
					if s.left!=nil{
						//左子树不为nil则以左子树为新的父级左子树
						s.parent.left=s.left
						s.left.parent=s.parent
					}
				}else if v>s.parent.data{//删除的是右子树

				}
			}
		}
	}
	return s
}

func (t *BiTree) Min() *BiNode {
	return t.FindMin(t.root)
}

func (t *BiTree) FindMin(node *BiNode) *BiNode {
	if node==nil{
		return nil
	}
	if node.left==nil{//如果左子树为空说明当前节点就是最小值
		return node
	}else {
		return t.FindMin(node.left)
	}
}
